The telecommunications industry has been expanding at an unprecedented growth rate. In particular, the wireless sector, including 3G, IEEE 802.11, wireless local area networks and Bluetooth devices, has grown far beyond expectations and at a much higher rate than the fixed telecommunications counterpart. The ability to access data and communicate anywhere at anytime has enormous potential and commercial value.
The content of the wireless sector is also changing, with more and more data being transmitted, including Internet connectivity and live feeds. The usage involving personal digital assistants (PDA's) and even smart appliances have created new markets utilizing wireless data communications. And, this wireless phenomenon is not limited to any geographical boundaries, as the growth is occurring around the globe.
Thus, despite the advancements in wireless transmission and reception, there is a growing problem of extracting more information signals within a limited bandwidth. Emerging multiple-access receiver processing procedures allow for multiple users to access the same communications medium to transmit or receive information. In addition to the problems associated with multiple users in a given bandwidth, an additional problem is the inability to process the data in the receivers in real time. Advanced receiver techniques cover several areas, namely interference suppression (also called multi-user detection), multipath combining and space-time processing, equalization, and channel estimation. These various techniques can be mixed and matched depending upon the circumstances. Proper signal processing of transmitter and receiver yield a far greater potential than current systems.
For example, a base station that processes a number of cellular devices has to receive and transmit data within a certain frequency range. The ability to extract the correct data from a given user is a difficult task, especially when the effects of interference and multipaths are considered. The problem is further complicated when the number of users exceeds the number of dimensions, resulting in an overloaded condition.
While the discussion herein illustrates wireless communications, the multiple access topologies are equally applicable to wired cable systems and local area networks, read/write operations of a disc drive, satellite communications and any application that benefits from manipulating digital data from among many multiple users.
In the past, communication systems generally utilized Frequency Division Multiple Access (FDMA) and Time Division Multiple Access (TDMA) methods to achieve channel access. FDMA refers to a communication channel wherein a signal's transmission power is concentrated into a single radio frequency band. Interference from adjacent channels is limited by the use of band pass filters however for each channel being assigned a different frequency system capacity is limited by the available frequencies and by limitations imposed by channel reuse.
In TDMA systems, a channel consists of a time slot or frame in a periodic train of time intervals over the same frequency, with a given signal's energy confined to one of these time slots. Adjacent channel interference is limited by the use of a time gate or other synchronization element that only passes signal energy received at the proper time. The system capacity is limited by the available time slots as well as by limitations imposed by channel reuse, as each channel is assigned a different time slot.
One of the goals of FDMA and TDMA systems is to try and prevent two potentially interfering signals from occupying the same frequency at the same time. In contrast, Code Division Multiple Access (CDMA) techniques allow signals to overlap in both time and frequency. CDMA signals share the same frequency spectrum and in the frequency or time domain, the CDMA signals appear to overlap one another. The scrambled signal format of CDMA eliminates cross talk between interfering transmission and makes it more difficult to eavesdrop or monitor calls therefore providing greater security.
In a CDMA system, each signal is transmitted using spread spectrum techniques. The transmitted informational data stream is impressed upon a much higher rate data stream termed a signature sequence. The bit stream of the signature sequence data is typically binary, and can be generated using a pseudo-noise (PN) process that appears random, but can be replicated by an authorized receiver. The informational data stream and the high bit rate signature sequence stream are combined by multiplying the two bit streams together, assuming the binary values of the two bit streams are represented by +1 or −1. This combination of the higher bit rate signal with the lower bit rate data stream is called spreading the informational data stream signal. Each informational data stream or channel is allocated a unique signature sequence.
In operation, a plurality of spread information signals, such as binary phase shift keying (BPSK) or quadrature phase shift keying (QPSK) modulation, modulate a radio frequency (RF) carrier and are jointly received as a composite signal at the receiver. Each of the spread signals overlaps all of the other spread signals, as well as noise-related signals, in both frequency and time. The receiver correlates the composite signal with one of the unique signature sequences, and the corresponding information signal is isolated and despread.
A signature sequence is normally used to represent one bit of information. Receiving the transmitted sequence or its complement indicates whether the information bit is a +1 or −1, sometimes denoted “0” or “1”. The signature sequence usually comprises N pulses, and each pulse is called a “chip”. The entire N-chip sequence, or its complement, depending on the information bit to be conveyed, is referred to as a transmitted symbol.
The receiver correlates the received signal with the complex conjugate of the known signature sequence to produce a correlation value. When a ‘large’ positive correlation results, a “0” is detected, and when a ‘large’ negative correlation results, a “1” is detected.
It should be understood that the information bits could also be coded bits, where the code is a block or convolutional code. Also, the signature sequence can be much longer than a single transmitted symbol, in which case a subsequence of the signature sequence is used to spread the information bit.
Further descriptions of CDMA communications techniques are described in U.S. Pat. No. 5,506,861. This patent describes radiotelephone communication systems, and in particular, receivers for jointly demodulating a plurality of CDMA signals with multipath time dispersion.
The prior systems do not properly account for the real world mobile communication signals that suffer from signal degradation such as interference and multipath problems. The systems of the state of the art generally tended to make assumptions that all other interferers and multipaths were additive white Gaussian noise. However, this assumption is not accurate for co-channel interference and multipaths.
Multipath dispersion occurs when a signal proceeds to the receiver along not one but many paths so that the receiver encounters echoes having different and randomly varying delays and amplitudes. Co-channel interference refers to signals received from other users either directly or reflected. The receiver receives a composite signal of multiple versions of the transmitted symbol that have propagated along different paths, called rays, having different relative time. Each distinguishable ray has a certain relative time of arrival, a certain amplitude and phase, and as a result, the correlator outputs several smaller spikes. RAKE receivers are well known and attempt to ‘rake’ together all the contributions to detect the transmitted symbol and recover the information bit.
Conventional RAKE receivers provide satisfactory performance under ideal conditions, however the signature sequence must be uncorrelated with time shifted versions of itself as well as various shifted versions of the signature sequences of the other CDMA signals. If one received signal corresponding to the signature sequence of interest has a non-negligible cross correlation with the received signal originating from another transmitter, then the value measured at the receiver, e.g. the correlation value for the signal of interest, is corrupted. In other words, the correlation computed at the receiver that would be used to decode a particular signal of interest is overwhelmed by an interfering signal; this is referred to as the near-far problem. The interference caused by an echo of one transmitted symbol overlapping with the next transmitted symbol must also be negligible. If this is not true, the transmitted symbols interfere with past and future transmitted symbols, commonly referred to as intersymbol interference (ISI). In actuality, performance is degraded by other signal interference and ISI.
There has been much research to address signal interference with known multipath time dispersion. This is termed joint demodulation with no multipath and is further described in S. Verdu, “Minimum Probability of Error For Asynchronous Gaussian Multiple-Access Channels,” IEEE Trans. Info. Theory, Vol. IT-32, pp. 85–96, R. Lupas and S. Verdu, “Linear multiuser detectors for synchronous code-division multiple-access channels,” IEEE Trans. Inform. Theory, Vol. 35, pp. 123–136, January 1989; and R. Lupas and S. Verdu, “Near-far resistance of multiuser detectors in asynchronous channels,” IEEE Trans. Commun., Vol. 38, pp. 496–508, April 1990.
There are a host of approaches for jointly demodulating any set of interfering digitally modulated signals, including multiple digitally modulated signals. Maximum Likelihood Sequence Estimation determines the most likely set of transmitted information bits for a plurality of digital signals without multipath time dispersion. The maximum likelihood joint demodulator is capable, in theory, of accommodating the largest number of interfering signals, but has a prohibitive computational complexity that makes it unrealizable in practice. The decorrelation receiver is another, less computationally complex receiver processing approach that zeroes out or decorrelates the different signals so that they no longer interfere with one another. The decorrelator as well as virtually every other lower complexity joint demodulator, is not capable of operation when the number of signals is over a set threshold which falls significantly short of the theoretical maximum.
In a real world multi-user system, there are a number of independent users simultaneously transmitting signals. These transmissions have the real-time problems of multi-path and co-channel interference, fading, and dispersion that affect the received signals. As described in the prior art, multiple user systems communicate on the same frequency and at the same time by utilizing parameter and channel estimates that are processed by a multi-user detector. The output of the multi-user detector is an accurate estimation as to the individual bits for an individual user.
Moreover, in an article by Paul D. Alexander, Mark C. Reed, John A. Asenstorfer and Christian B. Schlagel in IEEE Transactions on Communications, vol. 47, number 7, July 1999, entitled “Iterative Multi-User Interference Reduction: Turbo CDMA,” a system is described in which multiple users can transmit coded information on the same frequency at the same time, with the multi-user detection system separating the scrambled result into interference-free voice or data streams.
Low complexity multiuser detector have been contemplated that use linear multiuser detectors to achieve optimal near-far resistance. (Near-Far Resistance of Multiuser Detectors for Coherent Multiuser Communications, R. Lupas, S. Verdu, IEEE Trans. Commun. Vol 38, no. 4, pp 495–508, April 1990). While providing certain advantages, the performance has not been demonstrably improved. Varanasi and Aazhang proposed a multistage technique as described in the article Near-Optimum Detection in Synchronous Code-Division Multiple Access Systems, IEEE Trans. Commun., vol 39, No. 5, May 1991.
Decorrelating decision feedback detectors (DDFD) have been described by A. Duel-Hallen in Decorrelating Decision-Feedback Multiuser Detector for Synchronous Code-division Multiple Access Channel, IEEE Trans. Commun., vol 41, pp 285–290, February 1993. Wei and Schlegel proposed soft-decision feedback to suppress error propagation of the DDFD in Synchronous DS-SSMA with Improved Decorrelating Decision-Feedback Multiuser Detection, IEEE Trans. Veh. Technol., vol 43, pp 767–772, August 1994
Tree-type maximum-likelihood sequence detectors were also proposed for multiuser systems as were breadth-first algorithms and sequential detection including using the M-algorithm tree-search scheme with a matched filter (MF). The prior references also reveal schemes that include a decorrelating noise whitening filter (WF). There is even reference to combining a decorrelating noise whitening MF, and the M- and T-algorithms to provide near optimum performance at a low level of complexity compared with the optimal detector.
However, one of the primary disadvantages of the prior references implementations is the inability to accommodate overloaded conditions. Decision feedback techniques are limited in that they are incapable of working in supersaturated environments. Only the MMSE-based decision feedback detector can work in a supersaturated environment, however it is too aggressive with hypothesis testing to produce accurate results.
Another common problem is that the processing procedures in the receivers are difficult to run in real time. Advanced receiver techniques cover several areas, namely interference suppression (also called multi-user detection), multipath combining and space-time processing, equalization, and channel estimation. These various techniques can be mixed and matched depending upon the circumstances. Proper signal processing of transmitter and receiver yield a far greater potential than current systems.
Multi-user detection (MUD) refers to the detection of data in non-orthogonal multiplexes. MUD processing increases the number of bits available per chip or signaling dimension for systems having interference limited systems. A MUD receiver jointly demodulates co-channel interfering digital signals.
Optimal MUD based on the maximum likelihood sequence estimator operates by comparing the received signal with the entire number of possibilities that could have resulted, one for each bit or symbol epoch. Unfortunately, this processing is a computationally complex operation and it is not possible to accomplish in a real-time environment. Thus for those multi-user detectors that examine the entire space, real-time operation is often elusive.
In general, optimal MUD units function by examining a number of possibilities for each bit. However, for multi-user detectors that examine a larger capacity of signal, the computations are complex and time-consuming, thus making real-time operation impossible. Numerous attempts at reliable pruning of the optimal MUD decision process or the use of linear approximation to the replace the optimal MUD have still not produced a workable solution for the real world environment.
There are various multiuser detectors in the prior art, including optimal or maximum likelihood MUD, maximum likelihood sequence estimator for multiple interfering users, successive interference cancellation, TurboMUD or iterative MUD, and various linear algebra based multi-user detectors such as all of those detailed in the well-known text “Multiuser Detection” by Sergio Verdu. In basic terms, turbodecoding refers to breaking a large processing process into smaller pieces and performing iterative processing on the smaller pieces until the larger processing is completed. This basic principle was applied to the MUD.
There are several suboptimal multiuser detectors that are less computationally complex and known in the art. One example of suboptimal detectors, called linear detectors, includes decorrelators, minimum mean square error or MMSE detectors, and zero-forcing block linear equalizers. But, linear algebra based MUD (non-iterative) and successive interference cancellation fails for cases of overloaded multiple access systems. One example of overloading is where the number of simultaneous users is doubled relative to existing state of the art. Even for underloaded multiple access systems, the performance of non-iterative MUD and successive interference cancellation degrades significantly as the number of users increases, while the computation complexity of the optimal MUD increases significantly as the number of users increases. The computing problems are so extreme that it requires extensive and expensive hardware as well as complex processing. Moreover, an unreasonable delay would be required to decode each bit or symbol rendering such a system useless in practice.
Reduced complexity approaches based on tree-pruning help to some extent to eliminate the proper bit combination from consideration (i.e. prune the proper path in the decision tree) based on information from an unreliable bit estimate.
The M-algorithm is a pruning process that limits the number of hypotheses extended to each stage to a fixed tree width and prunes based on ranking metrics for all hypotheses and retaining only the M most likely hypotheses. The T-algorithm prunes hypotheses by comparing the metrics representing all active hypotheses to a threshold based on the metric corresponding to the most-likely candidate. Performance of M-algorithm based MUD degrades as the parameter M is decreased, but M governs the number of computations required. Similar effects are seen for other tree-pruning based MUD (T-algorithm, etc). To combat improper pruning, basic tree-pruning must ensure that M is “large enough”, and therefore still encounters increased complexity for acceptable performance levels when the number of interfering signals and/or ISI lengths are moderate to large.
As an illustration of the M-algorithm as a tree-pruning algorithm, consider a tree made up of nodes and branches. Each branch has a weight or metric, and a complete path is sequences of nodes connected by branches between the root of the tree and its branches. When applied as a short cut to the optimal MUD, each branch weight is a function of the signature signal of a certain transmitter, the possible bit or symbol value associated with that transmitter at that point in time, and the actual received signal which includes all the signals from all the interfering transmissions. The weight of each path is the sum of the branch metrics in a complete path. The goal of a tree searching algorithm is to try to find the complete path through a tree with the lowest metric. With the present invention the metrics of multiple complete paths are not calculated. Rather, the metrics of individual branches in a tree are calculated in the process of locating one complete path through the tree and thereby defines one unknown characteristic of each of the co-channel, interfering signals needed to decode the signals.
A MUD algorithm within the TurboMUD system determines discrete estimates of the transmitted channel symbols, with the estimates then provided to a bank of single-user decoders (one decoder for each user) to recover the input bit streams of all transmitted signals.
Two general types of multi-user detectors within the TurboMUD system are possible, namely those that provide hard outputs, which are discrete values, and those that provide soft outputs, which indicate both the discrete estimate and the probability that the estimate is correct.
However, single-user decoders operating on hard values, or discrete integers, have unacceptable error rates when there is a large amount of interference. The reason is that discrete integers do not provide adequate confidence values on which the single-user decoder can operate. These decoders operate better on so-called soft inputs in which confidence values can range from −1 to 1, such as for instance 0.75 as opposed to being either −1 or +1.
To provide soft values that can then be utilized by a single-user decoder, the multi-user detector can generate these soft values. However the processing takes an inordinate amount of time. Since single-user decoders operate best on soft values, it is often times the case that the computational complexity for a robust MUD capable of generating these soft values makes it impossible to get a real-time result.
In an attempt to provide real-time performance by reducing the computational complexity of an iterative multi-user detector that can produce soft values, the prior references suggests algorithms for examining less than the total number of possibilities for each of the bits of data that are coming in from the multiple users. The “shortcuts” taken by this reduced complexity approach cause errors and combating these errors by increasing the number of iterations of the system completely nullifies any advantage.
Thus, while the MUD unit can generate soft values within the iterative cycle of the TurboMUD, the entire detection system is slowed down in generating these soft values. It should be appreciated that these soft values, rather than being integers which would be considered to be hard values, are real numbers, which in effect, permit a single user decoder to better error correct the output of the multi-user detector and thereby provide a more robust bit stream that will faithfully represent the original input for a given user.
In general therefore, the optimum maximum likelihood multiuser detector (Verdu, Multiuser Detection, Cambridge University Press, 1998) or an M algorithm (as described, for instance, in Schlegel, Trellis Coding, IEEE Press, 1997) with a moderate to high value of M causes the Turbo MUD to require too many computations to keep up with real time transmissions. Using a fast inferior multiuser detection scheme such as a linear-based detector or those detailed in the text “Multiuser Detection” by Sergio Verdu causes poor quality output when there are many interferers or users.
Moreover, when dealing with hand-held communications units such as wireless handsets, the amount of processing within the device is limited, directly limiting the amount of computational complexity that is allowed. In order to provide real-time performance both at a cell site and the handset, it therefore becomes important to be able to reduce the amount of computational complexity and processing time so as to achieve real-time performance.
A further description of a TurboMUD system is described in an article by Paul D. Alexander, Mark C. Reed, John A. Asenstorfer and Christian B. Schlagel in IEEE Transactions on Communications, vol. 47, number 7, July 1999, entitled “Iterative Multi-User Interference Reduction: Turbo CDMA”, wherein multiple users transmit coded information on the same frequency at the same time.
The growing demand for radio communications raises the need to optimize the performance while maximizing the capacity of wireless communications systems. To optimize performance in a multi-user environment either interference must be eliminated (convention), or the number of interfering signals must be kept below a pre-determined number (virtually all non-optimum MUD techniques) which is typically far less than multiuser theory would allow. Existing approaches fail to address all of these problems. What is needed is an efficient signal processing technique to improve the quality and spectral efficiency of wireless communications and better techniques for sharing the limited bandwidth among different high capacity users. What is needed is an efficient signal processing technique to process communications channels in over-loaded conditions. Such a suboptimal system should efficiently estimate symbols and allow for real-time processing that does not exploit error correction codes. For commercial appeal, the invention should operate with existing transmitters and merely upgrade the receiver processing. Finally, the present system should allow more active transmissions in a given bandwidth without compromising performance. As can be seen, attempts to make real-time processing multi-user processing have been frustrated by complex and sophisticated hardware and processing requirements. What is needed therefore is a method and apparatus for allowing multiple users to operate in the same channel. Such a system should provide accurate cancellation of interfering signals while reducing complex processing.